package sword.T40;

import util.ListUtil;

import java.util.Arrays;
import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @Author: 18362
 * @Create: 2022-04-08 22:44:57 星期五
 */

class Solution {
    // 堆排序：空间复杂度O(k)、时间复杂度O(nlogk)
    /*public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0)
            return new int[]{};
        Queue<Integer> queue = new PriorityQueue<>((a, b) -> (b - a));
        for (int i=0; i<arr.length; ++i) {
            if (queue.size() < k) {
                queue.offer(arr[i]);
            } else {
                if (arr[i] < queue.peek()) {
                    queue.poll();
                    queue.offer(arr[i]);
                }
            }
        }
        int[] result = new int[k];
        int m = 0;
        Iterator<Integer> iterator = queue.iterator();
        while (iterator.hasNext()) {
            result[m++] = iterator.next();
        }
        return result;
    }*/

    // 快排：空间复杂度O(logk)，时间复杂度O(n)
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0)
            return new int[]{};
        return quickSort(arr, 0, arr.length-1, k);
    }

    private int[] quickSort(int[] arr, int left, int right, int K) {
        int pivot = partition(arr, left, right);
        if (pivot == K) {
            return Arrays.copyOf(arr, pivot);
        } else if (pivot > K) {
            return quickSort(arr, left, pivot, K);
        } else {
            return quickSort(arr, pivot+1, right, K);
        }
    }

    private int partition(int[] arr, int left, int right) {
        if (left >= arr.length)
            return arr.length;
        int i = left, j = right, base = arr[left];
        while (i < j) {
            while (i < j && arr[j] >= base)
                j--;
            arr[i] = arr[j];
            while (i < j && arr[i] <= base)
                i++;
            arr[j] = arr[i];
        }
        arr[i] = base;
        return i;
    }
}